package com.tgy.leetcode;



import java.util.*;
import java.util.concurrent.TimeUnit;


/**
 * @Author: tgy
 * @Date: 1/11/21 9:28 AM
 * <p>
 * https://leetcode-cn.com/problems/smallest-string-with-swaps/
 */
public class _1202_交换字符串中的元素 {

    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {


        if (s == null || s.length() <= 1) {

            return s;
        }
        char[] chars = s.toCharArray();
        int[] findUnion = new int[chars.length];

        for (int i = 0; i < findUnion.length; i++) {

            findUnion[i] = i;
        }

        for (List<Integer> pair : pairs) {

            union(findUnion,pair.get(0),pair.get(1));
        }

        Map<Integer,PriorityQueue<Character>> map = new HashMap<>();


        for (int i = 0; i < chars.length; i++) {

            int root = find(findUnion, i);

            PriorityQueue<Character> priorityQueue = map.get(root);

            if (priorityQueue == null) {

                priorityQueue = new PriorityQueue<>();
                map.put(root,priorityQueue);
            }

            priorityQueue.offer(chars[i]);
        }


        for (int i = 0; i < chars.length; i++) {

            int root = find(findUnion, i);
            chars[i] = map.get(root).poll();
        }


        return new String(chars);
    }

    private int find(int[] findUnion, int key) {


        if (findUnion[key] != key) {

//            key = findUnion[key];
            findUnion[key] = find(findUnion,findUnion[key]);
        }
        return findUnion[key];
    }


    private void union(int[]findUnion,int k1, int k2) {

        int r1 = find(findUnion, k1);
        int r2 = find(findUnion,k2);

        if (r1 != r2) {

            findUnion[r2] = r1;
        }
    }


    public static void main(String[] args) {

        _1202_交换字符串中的元素 smallestStringWithSwaps = new _1202_交换字符串中的元素();

        List<List<Integer>> pairs = new ArrayList<>();
//        pairs.add(new ArrayList<>(Arrays.asList(0, 3)));
//        pairs.add(new ArrayList<>(Arrays.asList(1, 2)));
//        pairs.add(new ArrayList<>(Arrays.asList(0, 2)));

        pairs.add(new ArrayList<>(Arrays.asList(2,3)));
        pairs.add(new ArrayList<>(Arrays.asList(3,2)));
//        pairs.add(new ArrayList<>(Arrays.asList(0,1)));
        pairs.add(new ArrayList<>(Arrays.asList(4,0)));
//        pairs.add(new ArrayList<>(Arrays.asList(4,0)));
        pairs.add(new ArrayList<>(Arrays.asList(3,2)));

//        pairs.add(new ArrayList<>(Arrays.asList(0, 2)));

        String result = smallestStringWithSwaps.smallestStringWithSwaps("qdwyt", pairs);

        System.out.println(result);

    }
}
